      1  import java.util.ArrayList;

      2  import java.util.List;

      3

      4  /**

      5     This program tests the red-black tree class.

      6  */

      7  public class RedBlackTreeTester

      8  {

      9     public static void main(String[] args)

     10     {

     11        testFromBook();

     12        insertionTest("ABCDEFGHIJ");

     13        removalTest(removalTestTemplate());

     14        System.out.println("All tests passed.");

     15     }

     16

     17     /**

     18        Runs the simple test from the textbook.

     19     */

     20     public static void testFromBook()

     21     {

     22        RedBlackTree t = new RedBlackTree();

     23        t.add("D");

     24        t.add("B");

     25        t.add("A");

     26        t.add("C");

     27        t.add("F");

     28        t.add("E");

     29        t.add("I");

     30        t.add("G");

     31        t.add("H");

     32        t.add("J");

     33        t.remove("A"); // Removing leaf

     34        t.remove("B"); // Removing element with one child

     35        t.remove("F"); // Removing element with two children

     36        t.remove("D"); // Removing root

     37        assertEquals("C E G H I J ", t.toString());

     38     }

     39

     40     /**

     41        Inserts all permutations of a string into a red-black tree and checks that

     42        it contains the strings afterwards.

     43        @param letters a string of letters without repetition

     44     */

     45     public static void insertionTest(String letters)

     46     {

     47        PermutationGenerator gen = new PermutationGenerator(letters);

     48        for (String perm : gen.getPermutations())

     49        {

     50           RedBlackTree t = new RedBlackTree();

     51           for (int i = 0; i < perm.length(); i++)

     52           {

     53              String s = perm.substring(i, i + 1);

     54              t.add(s);

     55           }

     56           assertEquals(letters, t.toString().replace(" ", ""));

     57        }

     58     }

     59

     60     /**

     61        Tests removal, given a template for a tree with a black node that

     62        is to be deleted. All other nodes should be given all possible combinations

     63        of red and black.

     64        @param t the template for the test cases

     65     */

     66     public static void removalTest(RedBlackTree t)

     67     {

     68        for (int m = 0; m <= 1; m++)

     69        {

     70           int nodesToColor = count(t.root) - 2; // We don't recolor the root or toDelete

     71           for (int k = 0; k < Math.pow(2, nodesToColor); k++)

     72           {

     73              RedBlackTree rb = new RedBlackTree();

     74              if (m == 0) { rb.root = copy(t.root); }

     75              else { rb.root = mirror(t.root); }

     76

     77              RedBlackTree.Node[] nodes = getNodes(rb);

     78              RedBlackTree.Node toDelete = null;

     79

     80              // Color with the bit pattern of k

     81              int bits = k;

     82              for (RedBlackTree.Node n : nodes)

     83              {

     84                 if (n == rb.root)

     85                 {

     86                    n.color = RedBlackTree.BLACK;

     87                 }

     88                 else if (n.color == RedBlackTree.BLACK)

     89                 {

     90                    toDelete = n;

     91                 }

     92                 else

     93                 {

     94                    n.color = bits % 2;

     95                    bits = bits / 2;

     96                 }

     97              }

     98

     99              // Add children to make equal costs to null

    100              int targetCost = costToRoot(toDelete);

    101              for (RedBlackTree.Node n : nodes)

    102              {

    103                 int cost = targetCost - costToRoot(n);

    104                 if (n.left == null) { n.setLeftChild(fullTree(cost)); }

    105                 if (n.right == null) { n.setRightChild(fullTree(cost)); }

    106              }

    107

    108              int filledSize = populate(rb);

    109              boolean good = true;

    110              try { checkRedBlack(rb); }

    111              catch (IllegalStateException ex) { good = false; }

    112              if (good)

    113              {

    114                 Comparable d = toDelete.data;

    115                 rb.remove(d);

    116                 checkRedBlack(rb);

    117                 for (Integer j = 0; j < filledSize; j++)

    118                 {

    119                    if (!rb.find(j) && !d.equals(j))

    120                    {

    121                       throw new IllegalStateException(j + " deleted");

    122                    }

    123                    if (rb.find(d))

    124                    {

    125                       throw new IllegalStateException(d + " not deleted");

    126                    }

    127                 }

    128              }

    129           }

    130        }

    131     }

    132

    133     /**

    134        Makes a template for testing removal.

    135        @return a partially complete red-black tree for the test.

    136        The node to be removed is black.

    137     */

    138     private static RedBlackTree removalTestTemplate()

    139     {

    140        RedBlackTree template = new RedBlackTree();

    141

    142        /*

    143                              n7

    144                             /  \

    145                            n1   n8

    146                           /  \

    147                         n0    n3

    148                              /  \

    149                             n2*  n5

    150                                  /\

    151                                n4  n6

    152        */

    153

    154        RedBlackTree.Node[] n = new RedBlackTree.Node[9];

    155        for (int i = 0; i < n.length; i++) { n[i] = new RedBlackTree.Node(); }

    156        template.root = n[7];

    157        n[7].setLeftChild(n[1]);

    158        n[7].setRightChild(n[8]);

    159        n[1].setLeftChild(n[0]);

    160        n[1].setRightChild(n[3]);

    161        n[3].setLeftChild(n[2]);

    162        n[3].setRightChild(n[5]);

    163        n[5].setLeftChild(n[4]);

    164        n[5].setRightChild(n[6]);

    165

    166        n[2].color = RedBlackTree.BLACK;

    167

    168        return template;

    169     }

    170

    171     /**

    172        Gets all nodes of this tree in sorted order.

    173        @param t a red-black tree

    174        @return an array of all nodes in t

    175     */

    176     private static RedBlackTree.Node[] getNodes(RedBlackTree t)

    177     {

    178        RedBlackTree.Node[] nodes = new RedBlackTree.Node[count(t.root)];

    179        getNodes(t.root, nodes, 0);

    180        return nodes;

    181     }

    182

    183     /**

    184        Gets all nodes of a subtree and fills them into an array.

    185        @param n the root of the subtree

    186        @param nodes the array into which to place the nodes

    187        @param start the offset at which to start placing the nodes

    188        @return the number of nodes placed

    189     */

    190     private static int getNodes(RedBlackTree.Node n, RedBlackTree.Node[] nodes, int start)

    191     {

    192        if (n == null) { return 0; }

    193        int leftFilled = getNodes(n.left, nodes, start);

    194        nodes[start + leftFilled] = n;

    195        int rightFilled = getNodes(n.right, nodes, start + leftFilled + 1);

    196        return leftFilled + 1 + rightFilled;

    197     }

    198

    199     /**

    200        Computes the cost from a node to a root.

    201        @param n a node of a red-black tree

    202        @return the number of black nodes between n and the root

    203     */

    204     private static int costToRoot(RedBlackTree.Node n)

    205     {

    206        int c = 0;

    207        while (n != null) { c = c + n.color; n = n.parent; }

    208        return c;

    209     }

    210

    211     /**

    212        Copies all nodes of a red-black tree.

    213        @param n the root of a red-black tree

    214        @return the root node of a copy of the tree

    215     */

    216     private static RedBlackTree.Node copy(RedBlackTree.Node n)

    217     {

    218        if (n == null) { return null; }

    219        RedBlackTree.Node newNode = new RedBlackTree.Node();

    220        newNode.setLeftChild(copy(n.left));

    221        newNode.setRightChild(copy(n.right));

    222        newNode.data = n.data;

    223        newNode.color = n.color;

    224        return newNode;

    225     }

    226

    227     /**

    228        Generates the mirror image of a red-black tree

    229        @param n the root of the tree to reflect

    230        @return the root of the mirror image of the tree

    231     */

    232     private static RedBlackTree.Node mirror(RedBlackTree.Node n)

    233     {

    234        if (n == null) { return null; }

    235        RedBlackTree.Node newNode = new RedBlackTree.Node();

    236        newNode.setLeftChild(mirror(n.right));

    237        newNode.setRightChild(mirror(n.left));

    238        newNode.data = n.data;

    239        newNode.color = n.color;

    240        return newNode;

    241     }

    242

    243     /**

    244        Makes a full tree of black nodes of a given depth.

    245        @param depth the desired depth

    246        @return the root node of a full black tree

    247     */

    248     private static RedBlackTree.Node fullTree(int depth)

    249     {

    250        if (depth <= 0) { return null; }

    251        RedBlackTree.Node r = new RedBlackTree.Node();

    252        r.color = RedBlackTree.BLACK;

    253        r.setLeftChild(fullTree(depth - 1));

    254        r.setRightChild(fullTree(depth - 1));

    255        return r;

    256     }

    257

    258     /**

    259        Counts the nodes in a tree

    260        @param n the root of a red-black tree

    261        @return the number of nodes in the tree

    262     */

    263     private static int count(RedBlackTree.Node n)

    264     {

    265        if (n == null) { return 0; }

    266        else { return 1 + count(n.left) + count(n.right); }

    267     }

    268

    269     /**

    270        Populates this tree with the values 0, 1, 2, ... .

    271        @param t a red-black tree

    272        @return the number of nodes in t

    273     */

    274     private static int populate(RedBlackTree t)

    275     {

    276        RedBlackTree.Node[] nodes = getNodes(t);

    277        for (int i = 0; i < nodes.length; i++)

    278        {

    279           nodes[i].data = new Integer(i);

    280        }

    281        return nodes.length;

    282     }

    283

    284     /**

    285        Checks whether a red-black tree is valid and throws an exception if not.

    286        @param t the tree to test

    287     */

    288     public static void checkRedBlack(RedBlackTree t)

    289     {

    290        checkRedBlack(t.root, true);

    291

    292        // Check that it's a BST

    293        RedBlackTree.Node[] nodes = getNodes(t);

    294        for (int i = 0; i < nodes.length - 1; i++)

    295        {

    296           if (nodes[i].data.compareTo(nodes[i + 1].data) > 0)

    297           {

    298              throw new IllegalStateException(

    299                 nodes[i].data + " is larger than " + nodes[i + 1].data);

    300           }

    301        }

    302     }

    303

    304     /**

    305        Checks that the tree with the given node is a red-black tree, and throws an

    306        exception if a structural error is found.

    307        @param n the root of the subtree to check

    308        @param isRoot true if this is the root of the tree

    309        @return the black depth of this subtree

    310     */

    311     private static int checkRedBlack(RedBlackTree.Node n, boolean isRoot)

    312     {

    313        if (n == null) { return 0; }

    314        int nleft = checkRedBlack(n.left, false);

    315        int nright = checkRedBlack(n.right, false);

    316        if (nleft != nright)

    317        {

    318           throw new IllegalStateException(

    319              "Left and right children of " + n.data

    320              + " have different black depths");

    321        }

    322        if (n.parent == null)

    323        {

    324           if (!isRoot)

    325           {

    326              throw new IllegalStateException(

    327                 n.data + " is not root and has no parent");

    328           }

    329           if (n.color != RedBlackTree.BLACK)

    330           {

    331              throw new IllegalStateException("Root "

    332                 + n.data + " is not black");

    333           }

    334        }

    335        else

    336        {

    337           if (isRoot)

    338           {

    339              throw new IllegalStateException(

    340                 n.data + " is root and has a parent");

    341           }

    342           if (n.color == RedBlackTree.RED

    343              && n.parent.color == RedBlackTree.RED)

    344           {

    345              throw new IllegalStateException(

    346                 "Parent of red " + n.data + " is red");

    347           }

    348        }

    349        if (n.left != null && n.left.parent != n)

    350        {

    351           throw new IllegalStateException(

    352              "Left child of " + n.data + " has bad parent link");

    353        }

    354        if (n.right != null && n.right.parent != n)

    355        {

    356           throw new IllegalStateException(

    357              "Right child of " + n.data + " has bad parent link");

    358        }

    359        if (n.color != RedBlackTree.RED && n.color != RedBlackTree.BLACK)

    360        {

    361           throw new IllegalStateException(

    362              n.data + " has color " + n.color);

    363        }

    364        return n.color + nleft;

    365     }

    366

    367     public static void assertEquals(Object expected, Object actual)

    368     {

    369        if (expected == null && actual != null ||

    370           !expected.equals(actual))

    371        {

    372           throw new AssertionError("Expected " + expected + " but found " + actual);

    373        }

    374     }

    375  }

    376

    377  /**

    378     This class generates permutations of a word.

    379  */

    380  class PermutationGenerator

    381  {

    382     private String word;

    383

    384     /**

    385        Constructs a permutation generator.

    386        @param aWord the word to permute

    387     */

    388     public PermutationGenerator(String aWord)

    389     {

    390        word = aWord;

    391     }

    392

    393     /**

    394        Gets all permutations of a given word.

    395     */

    396     public ArrayList<String> getPermutations()

    397     {

    398        ArrayList<String> permutations = new ArrayList<String>();

    399

    400        // The empty string has a single permutation: itself

    401        if (word.length() == 0)

    402        {

    403           permutations.add(word);

    404           return permutations;

    405        }

    406

    407        // Loop through all character positions

    408        for (int i = 0; i < word.length(); i++)

    409        {

    410           // Form a simpler word by removing the ith character

    411           String shorterWord = word.substring(0, i)

    412                 + word.substring(i + 1);

    413

    414           // Generate all permutations of the simpler word

    415           PermutationGenerator shorterPermutationGenerator

    416                 = new PermutationGenerator(shorterWord);

    417           ArrayList<String> shorterWordPermutations

    418                 = shorterPermutationGenerator.getPermutations();

    419

    420           // Add the removed character to the front of

    421           // each permutation of the simpler word,

    422           for (String s : shorterWordPermutations)

    423           {

    424              permutations.add(word.charAt(i) + s);

    425           }

    426        }

    427        // Return all permutations

    428        return permutations;

    429     }

    430  }